package funmath;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

/**
 *  （1）输入一个字符，当该字符是括号字符时候，程序进入循环处理
 *  (2)如果是左括号，则将其入栈，继续执行步骤(1)
 *  (3)如果是右括号，则取出栈顶数据进行比较，如果匹配不进行操作，否则必须先
 *  将刚才取出的栈顶数据重新入栈，再将刚才输入的括号字符也入栈
 *  (4)然后再输入下一个字符，重复执行，直到所有的字符都得到操作。
 *
 *  在本程序中的栈结构中，只能存放括号字符不能存放其他字符
 */
public class StackMatch {
    public static void main(String[] args) {
        String go;
        Scanner input = new Scanner(System.in);
        Stack stack = new Stack(20);
        System.out.println("括号匹配问题:");
        do {
            System.out.println("请先输入一组括号组合，用0标识结束，支持括号包括：{},(),[],<>");
            stack.piPei();
            System.out.println("继续玩么(y/n)?");
            go = input.next();
        } while ("y".equalsIgnoreCase(go));
        System.out.println("游戏结束！");
    }

    public static class Stack {
        public static final int NULL_FLAG = -1;
        public static final int SUCCESS_MATCH = 1;
        public static final int FAIL_MATCH = 0;
        private  char[] data;
        private int maxSize;
        private int top;

        public Stack(int maxSize) {
            this.maxSize = maxSize;
            data = new char[maxSize];
            top = NULL_FLAG;
        }

        public int getSize() {
            return maxSize;
        }
        //不是栈中有多少元素是栈的当前总下标
        public int getElementCount() {
            return top;
        }

        public boolean isEmpty() {
            return top == NULL_FLAG;
        }

        public boolean isFull() {
            return top + 1 == maxSize;
        }

        public boolean push(char data) {
            if (isFull()) {
                System.out.println("栈已满！");
                return false;
            }
            this.data[++top] = data;
            return true;

        }

        public char pop() throws Exception {
            if (isEmpty()) {
                throw new Exception("栈已空");
            }
            return this.data[top--];
        }

        public char peek() {
            return this.data[getElementCount()];
        }

        /**
         * 匹配方法要保证栈中存放的只有括号，栈里面不能有除了括号以外的字符
         */
        public   void piPei() {
            char ch, temp;
            int match;
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            try {
                ch = (char) reader.read();//输入一个字符
                while (ch != '0') {
                    if (getElementCount() == NULL_FLAG) {
                        push(ch);
                    } else {
                        temp = pop();//取出栈顶元素
                        match = 0;
                        if (temp == '(' && ch == ')') {  //判断是否匹配
                            match = SUCCESS_MATCH;
                        }
                        if (temp == '[' && ch == ']') {
                            match = SUCCESS_MATCH;
                        }
                        if (temp =='<' && ch == '>') {
                            match = SUCCESS_MATCH;
                        }
                        if (match == FAIL_MATCH) {//如果不匹配
                            push(temp); //原栈顶元素重新入栈
                            push(ch);  //将输入的括号字符入栈
                        }
                    }
                    ch = (char) reader.read(); //输入一个字符
                }
                if (getElementCount() == NULL_FLAG) {
                    System.out.println("输入的括号完全匹配！");//完全匹配
                } else {
                    System.out.println("输入的括号不匹配，请检查!"); //不完全匹配
                }
            } catch (Exception e) {
                e.printStackTrace();
            }

        }
    }
}